package com.xcoder.algorithm.sort;

import java.util.logging.Level;

/**
 * 快速排序
 * <p>
 * 思路：
 * 1.先从数组中取出一个数作为基准数；
 * 2.分区过程，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边；
 * 3.再对左右区间重复第二步，直到各区间只有一个数
 */
public class QuickSort {

    public static void main(String[] args) {
        int[] a = {7, 1, 2, 3, 4, 5, 6};
//        int[] a = {1, 2, 3, 1, 2, 3, 0};
//        int[] a = {2, 1, 4, 0, 12, 32, 2, 9, 5, 3, 12, 14};
        quickSort(a, 0, a.length - 1);
        System.out.print("排序结果：");
        for (int i : a) {
            System.out.print(i + " ");
        }
    }

    private static void quickSort(int[] arr, int start, int end) {
        if (start < end) {
            int pivotIndex = getPivotIndex(arr, start, end);
            // 对轴点左右子数组进行快速排序
            quickSort(arr, start, pivotIndex - 1);
            quickSort(arr, pivotIndex + 1, end);
        }
    }

    private static int getPivotIndex(int[] arr, int start, int end) {
        // 为了避免最坏情况(如：7123456)，一般要随机选择轴点元素
//        swap(arr, start, start + (int) (Math.random() * (end - start)));

        int pivot = arr[start];
        while (start < end) {
            while (end > start) {
                // 从右往左找第一个小于等于x的数，等于也换是为了保证左右尽量均匀
                if (arr[end] <= pivot) {
                    // 找到了将其放到start位置
                    arr[start] = arr[end];
                    start++;
                    break;
                } else {
                    end--;
                }
            }

            while (start < end) {
                // 从左往右找第一个大于等于x的数
                if (arr[start] >= pivot) {
                    // 找到了将其放到end位置
                    arr[end] = arr[start];
                    end--;
                    break;
                } else {
                    start++;
                }
            }
        }
        // 最终start=end，将轴点元素放入该位置
        arr[start] = pivot;
        return start;
    }

}
